In a field of advanced research and development, a higher level/complexity thereof has made a great many trials and errors absolutely necessary, increasing risks on the way of developments. In Japan that depends on science and technology for its survival, it is extremely important to achieve an unprecedentedly high level/efficiency of a development process by eliminating such risks as many as possible.
In the field of research and development, computer aided design (CAD), computer aided manufacturing (CAM), computer aided engineering (CAE), computer aided testing (CAT), and the like are currently used as simulation means of designing, fabricating, analyzing and testing.
Moreover, according to the present invention, cooperative simulation (C-Simulation) which is continuous simulation, advanced CAM (A-CAM) which takes a fabrication process into consideration, deterministic fabrication (D-fabrication) which can achieve ultimate accuracy and the like must come into wide use.
According to such conventional simulation means, data of an object is stored based on constructive solid geometry (CSG) or boundary representation (B-rep).
In the case of CSG, however, the entire object is stored as an aggregation of very small solid models. Consequently, if data is heavy and simulation means (software or the like) is mounted, enormous data must be processed, causing a problem of much time necessary for analysis even when a large scale computer is used.
In the case of the B-rep, the object is represented by a boundary. Thus, while data is light and an amount of data is small, there is no direct information regarding the inside of a boundary surface, causing a problem of unsuitability to deformation analysis.
Furthermore, according to the conventional data storage means, each time thermal/fluid analysis, large solid analysis, coupled analysis thereof or the like is carried out, division is made in a mesh form suited to the analysis, and a result of the analysis can be displayed to apply a finite element method. However, unification of CAD and simulation is difficult, causing a problem of impossibility of managing the processes of designing, analyzing, fabricating, assembling, testing and the like based on the same data.
In other words, the following problems are inherent in the current solid/surface-CAD (referred to as S-CAD hereinafter):    (1) data is not passed, inferior in internal conversion operation (problems of numerical value error and processing method);    (2) direct use is impossible for simulation (mesh must be formed because there is not any internal information); and    (3) investigation of fabrication by CAM is impossible (only last shape is given).
Additionally, the following problems are inherent in fabrication:    (1) a fabrication process cannot be represented (rough fabrication or process design assistance is insufficient);    (2) dealing with a new fabrication method such as laser fabrication or superadvanced fabrication is impossible (only cutting is available, numerical value accuracy is insufficient); and    (3) a fabrication method itself cannot be selected (different material characteristics are given in compound material).
To solve the aforementioned problems, the inventors et. al have invented “Method for storing substantial data that integrates shape and physical properties”, and filed a patent application [Patent Document 1].
According to this invention, as schematically shown in FIG. 1, external data constituted of boundary data of an object is divided into cubic cells by oct-tree division in which boundary surfaces cross each other at right angles, and the divided cells are classified into an internal cell 13a positioned inside and outside of the object and a boundary cell 13b which includes a boundary surface. In the drawing, a reference numeral 15 is a cutting point.
According to this invention, various physical property values are stored for each cell, and substantial data that integrates shapes and physical properties can be stored by a small storage capacity. Thus, a shape, a structure, physical property information, and hysteresis of the object are managed in a unified manner to enable management of data regarding a series of processes from designing to fabricating, assembling, testing, evaluation and the like based on the same data, whereby it is possible to unify CAD and simulation.
Furthermore, the present inventors have invented “Conversion method and conversion program of three-dimensionally shaped data into cell internal data”, and filed a patent application [Patent Document 2].
According to the present invention, it is possible to form, from external data, cell internal data capable of dividing a surface very accurately approximated to a curved surface having a large curvature into triangular meshes without forming any triangle having unsatisfactory gap or accuracy, while retaining continuity from an adjacent cell in a volume CAD.
[Patent Document 1]
Japanese Patent Application Laid-Open No. 2002-230054, “Method for storing substantial data that integrates shape and physical properties”
[Patent Document 2]
Japanese Patent Application No. 2001-370040, “Conversion method and conversion program of three-dimensional shape data into cell internal data”, not laid open
[Patent Document 3]
Japanese Patent Application Laid-Open No. 2003-44528, “Method of generating surface lattice of object”
[Patent Document 4]
Japanese Patent Application No. 2003-131313, “Method and program for identifying multimedia data”, not laid open
[Non-Patent Document 1]
K. Kase, Y. Teshima, S. Usami, H. Ohmori, C. Teodosiu, and A. Makinouchi “Volume CAD” International Workshop on Volume Graphics (VG 03), 2003, Tokyo. Japan.(to appear).
[Non-Patent Document 2]
Y. Teshima, S. Usami, and K. Kase“Shape Approximation, Cube Cutting and Enumeration”, The Institute of Statistical Mathematics, Tokyo, Japan,Abstract pp9.
[Non-Patent Document 3]
Y. Teshima, S. Usami, and K. Kase, “Enumeration on Cube Cutting”, Japan Conference on Discrete and Computational Geometry , 2002, Tokyo, Japan. pp. 87-88,
[Non-Patent Document 4]
C. M. Hoffmann, “The Problems of accuracy and robustness in geometric computation.”, Computer, 22 (3):pp31-41, 1989
[Non-Patent Document 5]
T. Ju, F. Losasso, S. Shaefer, J. Warren, “Dual Contouring of Hermite Data”, Siggraph2002, Italy, proc. pp339-346
[Non-Patent Document 6]
W. J. Shroeder, “A Topology Modifying Progressive Decimation Algoritm”, Proc. Visuallizatin97, pp205-212, October 1997
[Non-Patent Document 7]
W. J. Shroeder, J. A. Zarge and W. E. Lorensen, “Decimation of Triangle Meshes”, Proc. Siggraph 92, pp65-70, July 1992
[Non-Patent Document 8]
K. J. Renze and J. H. Oliver, “Generalized Surface and Volume Decimation for Unstructured Tessellated Domains”, Proc. VRAIS96, pp111-121, March 1996
[Non-Patent Document 9]
B. Hamman, “A Data Reduction Scheme for Triangulated Surfaces,” CAGD, 11(2)
[Non-Patent Document 10]
I. Navazo, “Extended Octtree Representation of General Solids with Plane Faces: Model Structure and Algorithms”, Computer and Graphics Vol. 13, No. 1, pp5-16, 1989
[Non-Patent Document 11]
H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle, “Mesh Optimization”, Proc. Siggraph93, pp. 19-26, August 1993
[Non-Patent Document 12]
H. Hoppe, “Progressive Meshes” Proc. Siggraph96 pp99-108, August 1996
[Non-Patent Document 13]
P. Lindstrom and G. Turk, “Evaluation of Memoryless Simplification” IEEE tvcg, 5(2), pp98-115, April-June 1999,
[Non-Patent Document 14]
M. Garland and P. S. HEckbert, “Surface Simplification Using Quadric Error Metrics,” Proc. SIGGRAPH 97, pp. 209-216, August 1997.
[Non-Patent Document 15]
C. M. Hoffmann. The problems of accuracy and robustness in geometric computation. Computer, 22(3):31-41, 1989.
[Non-Patent Document 16]
K. Sughihara and M. Iri. A solid modeling system free from topological inconsistency. Journal of Information Processing, 12:380-393, 1989.
[Non-Patent Document 17]
A. Kela. Hierarchical octree approximations for boundary representation-based geometric models, Computer-Aided Design, 21(6):355-362, 1989.
[Non-Patent Document 18]
I. Navazo, D. Ayala and P. Brunet. A geometric modeller based on the exact octtree representation of polyhedra, Computer Graphics Forum (Eurographics '86 Proc.):591-104, 1986.
[Non-Patent Document 19]
W. Lorensen and H. Cline. H. Marching cubes: high resolution 3D surface construction algorithm. ACM Computer Graphics (Proc. of ACM SIGGRAPH '87), 21(4):163-169, 1987.
[Non-Patent Document 20]
I. Navazo, D. Ayala, and P. Brunet “A Geometric Modeller Based on the Exact Octtree Representation of Polyhedra”, Computer Graphics Forum 5 pp91-104, 1986
[Non-Patent Document 21]
T. Hama, M. Asakawa, M. Takamura, A. Makinouchi, C. Teodosiu, “A stable and fast new contact search algorithm for FEM simulation of metal forming process”, (to appear)
As proposed in [Non-Patent Document 1] and [Patent Document 1], a method for generating shape representation by a cell and a triangle patch adapted to the cell, and data is conducted in the following three steps.    (Step 1) calculation of intersection point between a cell space defined by a user and the triangle patch as an input shape (calculation of cell cutting points)    (Step 2) A closed loop is generated which can be obtained by connecting cell cutting points for each cell on a cell surface. In this case, the loop is determined in order from a loop uniquely determined based on the number of cell cutting points or a relation between the adjacent cell.    (Step 3) The closed loop generated in each cell is divided into triangles based on a difference from the input shape.
However, this method has the following problems.    (1) There is a case where the process of (Step 2) is not completed with respect to a shape which has the same degree of complexity as that of a cell size.    (2) A non-various shape is generated while the shape gradually changes from a shape having a size finer than the cell size to a large shape, and therefore there is a case of failure in the process of (Step 2).    (3) In a case where hierarchizing of the cells is considered, it is remarkably difficult to search for an adjacency relation in the process of (Step 2).
As means for solving these problems, means has been required in which phase information of the triangle patch as the input shape is used as such, and the shape is simplified if necessary.
It is to be noted that a method of dividing the triangle patch into the cell sizes to manage the cells is also proposed in [Patent Document 3]. However, in this method, the triangle patch is not adapted to the cell, and the cell and the triangle patch cannot be managed in one-to-one correspondence. The method cannot be applied to an object of V-CAD which is unified data management from upstream to downstream steps in manufacturing.
Moreover, as to a process in the triangle patch alone, Hoppe [Non-Patent Document 11] or the like has proposed a method of segmentizing/integrating the triangle patches to thereby detail/simplify shape representation [Non-Patent Document 12], and there exist parameters or a dividing method for the sementizing, and various derived systems depending on judgment standards at an integrating time. However, in these methods, there is used a conversion method in which two-various-article conditions and phase conditions of an original shape are taken over as such, and the methods are not suitable for an operation to intentionally simplify micro shapes or the like [Non-Patent Documents 6, 7, and 8].